// --------------------------
// projects/c++/3n+1/main.c++
// Copyright (C) 2009
// Original Stub Code by Glenn P. Downing
// Modified by Ben Menchaca
// --------------------------

// To run the tests:
//     g++ -ansi -pedantic -lcppunit -ldl -Wall -DTEST main.c++ -o main.app
//     valgrind main.app

// To run the program:
//     g++ -ansi -pedantic -Wall main.c++ -o main.app
//     valgrind main.app < main.in > main.out
// To document the program:
//     doxygen Doxyfile

#include <cassert>  // assert
#include <iostream> // cin, cout, endl, ios_base, istream, ostream

#ifdef TEST
#include "cppunit/TestSuite.h"      // TestSuite
#include "cppunit/TextTestRunner.h" // TestRunner
#endif // TEST

/**
 * input i: don't change after reading.  May be <, > or = to j.
 */
int i = 0;

/**
 * input j: don't change after reading.  May be <, > or = to i.
 */
int j = 0;

/**
 * The output value for main.
 */
int v = 0;

/******************************************************************************
 * CACHE IMPLEMENTATION
 *****************************************************************************/
#ifdef NDEBUG
/**
 * Size of the cache of previously computed length values.
 */
#define CACHE_SIZE			131072

/**
 * Cache of previously computed cycle length values for a given input.  The
 * cache's key is the value who's cycle length we want.  If the value is 0,
 * This indicates that this value has not yet been cached.  Initialized to all
 * zeroes.
 */
static unsigned int cache[CACHE_SIZE]={0};
#else
#include "cache.h"
/**
 * All cycle lengths for any value smaller than 1,000,000 should be less than
 * this.
 */
#define MAX_CYCLE_LENGTH		1000
/**
 * Largest value that will be provided as inputs i or j.
 */
#define MAX_ALLOWED_VALUE		1000000
/** If we are in debug mode, make the cache too large so we can check bounds.*/
unsigned int cache[CACHE_SIZE + 1]={0};
#endif
 


/**
 * @brief Searches for a cycle length stored in the cache for a given value.
 * @param value The value for which we should search.
 * @pre No constraints on the value, although values larger than CACHE_SIZE
 * will never be cached.
 * @invariant No cache entries are modified by this operation.
 * @post No cache entries are modified.
 * @return Either the cycle length if this value was cached, or zero if either
 * the value is too large to be cached, or if this value has not yet been
 * cached.
 */
static inline unsigned int cache_lookup(unsigned int value)
{
	if (value < CACHE_SIZE) {
		assert(cache[value] < MAX_CYCLE_LENGTH);
		return cache[value];
	}

	return 0;
}



/**
 * @brief Stores a calculated cycle length for a particular value.
 * @param value The value for which we have a calculated cycle length.  
 * @param len The calculated cycle length.  This value must be less than
 * MAX_CYCLE_LENGTH.
 * @pre The value in the cache must have previously been the empty value (0).
 * @invariant The only cache entry modified is the entry corresponding to
 * value, and it is modified iff value < CACHE_SIZE.
 * @post The entry corresponding to value now caches the value len iff value <
 * CACHE_SIZE.  
 */
static inline void cache_store(unsigned int value, unsigned int len)
{
	assert(len < MAX_CYCLE_LENGTH);
	if (value < CACHE_SIZE) {
		assert(cache[value] == 0);
		cache[value] = len;
	}
}



/******************************************************************************
 * PRIMARY CYCLE LENGTH CALCULATIONS AND UTILITIES
 *****************************************************************************/
/*!
 * @brief Takes an unsigned integer and determines if it is even: (n % 2) == 0.
 * @param value integer to check; any unsigned integer is valid.
 * @return True iff the value is even, and false otherwise.
 * @pre No constraints on value, and no preconditions.
 * @invariant none
 * @post No change in value or any internal state.
 */
static inline bool is_even(unsigned int value)
{
	return ((value & 1) == 0);
}



/*!
 * @brief Calculates the cycle length for the given value, and returns the
 * calculated cycle length.
 * @param value The value who's cycle length we are to calculate. 
 * @pre All conditions for value must be met.
 * @invariant No cache state is modified iff the value is not produced during
 * the calculation of the cycle length.
 * @post For every value calculated in computing the cycle length, if it meets
 * the caching criteria, the cycle length is cached.
 * @note This function is recursive, and is only guaranteed to work for a
 * subset of initial values < MAX_ALLOWED_VALUE.  The caller is responsible
 * for not providing initial values to this function that would cause integer
 * overflow during the calculation of the cycle length.
 */
unsigned int cycle_length(unsigned int value)
{
	unsigned int len, cached_len;

	cached_len = cache_lookup(value);
	if (cached_len > 0) return cached_len;

	if (is_even(value)) {
		// n / 2 = n >> 1
		len = 1 + cycle_length(value >> 1);
	} else {
		// 3n + 1 = 2n + n + 1 = (n << 1) + n + 1
		len = 1 + cycle_length((value << 1) + value + 1);
	}
	cache_store(value, len);
	return len;
}

/**
 * @brief Computes the max cycle length in the range [i, j] and stores the
 * result in v.
 * @pre Assumes that the values i and j have been initialized, and are
 * non-zero.  These values need not be ordered.
 * @invariant i and j are not modified.  The cache will be modified, as the
 * cache rules in specify.
 * @post v contains the longest cycle length over the range [i, j].
 * @see cycle_length
 */
void eval()
{
	unsigned int k, len, lower, upper;

	lower = (i < j) ? i : j;
	upper = (i < j) ? j : i;

	v = 0;
	for (k = lower; k <= upper; k++) {
		len = cycle_length(k);
		if (v < len) v = len;
	}
}


/******************************************************************************
 * I/O ROUTINES
 *****************************************************************************/
/**
 * @brief reads an int into i and j from the given input stream.
 * @param in The input stream from which we read.
 * @return true iff the read succeeds, false otherwise
 */
bool read (std::istream& in) {
	if (!(in >> i)) {
		return false;
	}
	in >> j;
	return true;
}


/**
 * @brief prints the values of i, j, and v to the given output stream.
 * @param out The output stream to which we should write.
 */
void print (std::ostream& out) {
	out << i << " " << j << " " << v << std::endl;
}

/******************************************************************************
 * MAIN
 *****************************************************************************/
#ifdef TEST
#include "TestCollatz.h"
#endif
/**
 * @brief either runs the tests or runs the program
 * @return 0 in all cases.
 */
int main () {
	using namespace std;
	ios_base::sync_with_stdio(false);     // turn off synchronization with C I/O
	/* Initialize the base-case value */
	cache[1] = 1;
#ifdef TEST
	using namespace CppUnit;
	TextTestRunner tr;
	tr.addTest(TestCollatz::suite());
	tr.run();
#else
	while (read(cin)) {
		eval();
		print(cout);
	}
#endif // TEST

	return 0;
}
